package com.taobao.ad.hadoop.common;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class TopK {
	private TopK(){ 
	} 
	private static Random rnd = new Random();
	public static Comparator<Pair> cmp = new Comparator<Pair>() { 
		@Override
		public int compare(Pair p1, Pair p2) { 
			return -p1.compareTo(p2);
		} 
	};
	public static List<Pair> getTopK1(List<Pair> pairList,int k){
		Heap heap = new Heap();
		heap.setHeapSize(k);
		for(Pair pair: pairList){
			heap.push(pair);
		}
		heap.sort();
		List<Pair> list = heap.getData();
		return list;
	}
	
	public static List<Pair> getTopK2(List<Pair> pairList, int k){
		List<Pair> list1 = new ArrayList<Pair>();
		List<Pair> list2 = new ArrayList<Pair>(); 
		Pair pivot = pairList.get(Math.abs(rnd.nextInt()) % pairList.size());
		for(Pair pair: pairList){
			if(pivot.compareTo(pair) <= 0){
				list1.add(pair);
			}else{
				list2.add(pair);
			}
		}
		if(list1.size() == k){
			Collections.sort(list1,cmp);
			return list1;
		}else if(list1.size() > k){
			return getTopK2(list1, k);
		}else{
			Collections.sort(list1,cmp);
			list1.addAll(getTopK2(list2, k - list1.size()));
			return list1;
		}
	}
	public static List<Pair> getTopK3(List<Pair> pairList, int k){
		List<Pair> list = new LinkedList<Pair>();
		for(Pair pair: pairList){ 
			if(list.size() == 0){
				list.add(pair);
				continue;
			}
			int index = 0;
			for(Pair p: list){
				if(index == k){
					break;
				}
				if(pair.compareTo(p) <= 0){  
					if(++ index == list.size()){
						list.add(pair);
						break;
					} 
					continue;
				}else{
					list.add(index, pair);
					break;
				}
			}
		}
		return list.subList(0, k);
	}
	public static List<Pair> getTopK4(List<Pair> pairList, int k){
		Collections.sort(pairList,cmp);
		return pairList.subList(0, k);
	}
}
